/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package search;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import plot.GNUPlot;
import world.Point;

/**
 *
 * @author dheath
 */
public class DepthFirstSearch implements Search 
{
    private int nodesChecked;
    private double totalCost;
    private double diag;
    
    public PriorityNode searchWorld(WorldNode start, WorldNode end, GNUPlot plot)
    {
        nodesChecked = 0;
        double accCost = 0.0;
        diag = Math.sqrt(start.getLength() * start.getLength() + start.getLength() * start.getLength()) - start.getLength();
        
        Stack<WorldNode> path = new Stack();
        Set<WorldNode> visited = new HashSet();
        
        System.out.println("Starting search...");
        if(searchWorld(start,path,end,visited,plot, accCost))
        {
            plotPath(path,plot);
        }
        else
        {
            plotPath(path,plot);
        }
        return null;
    }
    
    private void plotSouth(WorldNode current, GNUPlot plot)
    {
        //System.out.println(current.getCost());
        if(current.getSouth() != null)
        {
            plot.printLine(current.getCenter(), current.getSouth().getCenter(), 1, true);
            plotSouth(current.getSouth(), plot);
        }
    }
    
    
    private void plotPath(Stack<WorldNode> path, GNUPlot plot)
    {
        int num = 0;
        if(!path.isEmpty())
        {
            WorldNode start = path.pop();
            while(!path.isEmpty())
            {  
                num++;
                WorldNode end = path.pop();
                plot.printLine(start.getCenter(),end.getCenter() , 2,true);
                start = end;
            }
        }
        System.out.println("TOTAL NODES IN PATH: "+num);
        System.out.println("TOTAL COST OF PATH: "+totalCost);
        System.out.println("Nodes expanded: "+nodesChecked);
    }
    
    private boolean searchWorld(WorldNode current, Stack<WorldNode> path, WorldNode end, Set<WorldNode> visited,GNUPlot plot, double accCost)
    {
      
       if(!visited.contains(current))
       { 
           nodesChecked++;
           visited.add(current);
           path.push(current);
           plot.printX(current.getCenter(), 1);
           plot.printNode(current.getCenter(), 1);
           if(current == end)
           {
               totalCost = accCost;
               return true;
           }
           else
           {
               
               if(current.getWest() != null && current.getWest().getCost() < Double.POSITIVE_INFINITY)
               {
                  // System.out.println("searching west");
                   if(searchWorld(current.getWest(),path,end,visited,plot,accCost + current.getWest().getCost()))
                   {
                       return true;
                   }
               }
               
               if(current.getSouthWest() != null && current.getSouthWest().getCost() < Double.POSITIVE_INFINITY)
               {
                   if(searchWorld(current.getSouthWest(),path,end,visited,plot,accCost + current.getSouthWest().getCost()+diag))
                   {
                       return true;
                   }
               }
               if(current.getSouth() != null && current.getSouth().getCost() < Double.POSITIVE_INFINITY)
               {
                   //System.out.println("searching south");
                   if(searchWorld(current.getSouth(),path,end,visited,plot,accCost + current.getSouth().getCost()))
                   {
                       return true;
                   }
               }
               if(current.getSouthEast() != null && current.getSouthEast().getCost() < Double.POSITIVE_INFINITY)
               {
                   if(searchWorld(current.getSouthEast(),path,end,visited,plot,accCost + current.getSouthEast().getCost()+diag))
                   {
                       return true;
                   }
               }
               if(current.getEast() != null && current.getEast().getCost() < Double.POSITIVE_INFINITY)
               {
                   //System.out.println("searching east");
                   if(searchWorld(current.getEast(),path,end,visited,plot,accCost + current.getEast().getCost()))
                   {
                       return true;
                   }
               }
               if(current.getNorthEast() != null && current.getNorthEast().getCost() < Double.POSITIVE_INFINITY)
               {
                   if(searchWorld(current.getNorthEast(),path,end,visited,plot,accCost + current.getNorthEast().getCost()+diag))
                   {
                       return true;
                   }
               }
               if(current.getNorth() != null && current.getNorth().getCost() < Double.POSITIVE_INFINITY)
               {
                   //System.out.println("searching north");
                   if(searchWorld(current.getNorth(),path,end,visited,plot,accCost + current.getNorth().getCost()))
                   {
                       return true;
                   }
               }
               if(current.getNorthWest() != null && current.getNorthWest().getCost() < Double.POSITIVE_INFINITY)
               {
                   if(searchWorld(current.getNorthWest(),path,end,visited,plot,accCost + current.getNorthWest().getCost()+diag))
                   {
                       return true;
                   }
               }
               
               path.pop();
               return false;
           }
       }
       else
       {
            //System.out.println("already on stack");
           return false;
       }
              
    }


}
